package leetcode;

/**
 * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 * <p>
 * 示例：
 * <p>
 * 给定一个链表: 1->2->3->4->5, 和 n = 2.
 * <p>
 * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
 *
 * @author: cuihao
 * @create: 2020-06-30 02:22
 **/
public class RemoveNthFromEnd {

    /**
     * @param head
     * @param n
     * @return
     */
    public ListNode solution(ListNode head, int n) {
        if (head == null) {
            return null;
        }

        ListNode temp = head;
        int length = 0;
        while (temp != null) {
            length++;
            temp = temp.next;
        }

        if (n == length) {
            head = head.next;
            return head;
        }

        ListNode node = head;
        // 要删第count后面的 所以先找到第count个
        int count = length - n;
        while (count > 1) {
            node = node.next;
            count--;
        }

        if (node.next != null) {
            node.next = node.next.next;
        } else {
            node.next = null;
        }
        return head;

    }

    /**
     * 双指针、脑子不够用 别用这个
     *
     * @param head
     * @param n
     * @return
     */
    public ListNode solution1(ListNode head, int n) {
        ListNode dummy = new ListNode(0);

        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        for (int i = 0; i < n; i++) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
